/**
 * 给定一个字符串T，再给定字符串数组S，Si有代价Ci
 * 问用Si拼成T的最小代价是多少？Si可以使用任意次
 * DP方程很简答，令Di是从i位置开始拼到结尾的最小代价
 * 则 Di = min(D[i + Lk] + Ck, 满足Sk == T.substr(i, Lk)，Lk是Sk的长度)
 * 如果遍历以i开头的所有长度，则是O(N^2)的，必然超时。
 * 因此需要从候选者的角度考虑。
 * 考虑到Si的长度和不会超过5E4，因此候选长度是有限的，具体而言是sqrt(5E4)。
 * 因此只需要O(N * sqrt(N))完成循环，再然后需要考虑判字符串相等，显然用哈希。 * 
 * 因此首先做个查重，S中相等的字符串只留下代价最小的
 * 然后按照长度构造map。map[i]保存长度为i的所有字符串的哈希与代价
 * 
 * for i in range(N - 1, -1, -1):
 *     for len, vec in Map:
 *         if i + len 超过T的全长: break
 *         if D[i + len] == -1: continue # 说明 i + len 拼不出来
 *         令h是T.substr(i, len)的哈希，这个可以O(1)得到
 *         在vec中查找h，如果是哈希表可以O(1)完成，map则O(logN)完成
 *         找到了就更新DP状态
 * 最后D[0]是答案
 * 
 * 确定好枚举对象后，唯一的问题就是快速判断匹配，这里用的子串哈希
 * 还可以用后缀数组和AC自动机。
 */
namespace ZIFUCHUAN
{

int const UN = 2;

using hash_t = array<size_t, UN>;
// 10007, 10093
hash_t const Seeds {13313, 10}; // 10用来观察效果
hash_t const ZERO {0, 0};
hash_t const ONE {1, 1};

hash_t const operator + (const hash_t & a, const hash_t & b){
    hash_t ans;
    for(int i=0;i<UN;++i) ans[i] = a[i] + b[i];
    return ans;
}

hash_t const operator - (const hash_t & a, const hash_t & b){
    hash_t ans;
    for(int i=0;i<UN;++i) ans[i] = a[i] - b[i];
    return ans;
}

hash_t const operator * (const hash_t & a, const hash_t & b){
    hash_t ans;
    for(int i=0;i<UN;++i) ans[i] = a[i] * b[i];
    return ans;
}

ostream & operator << (ostream & os, const hash_t & h) {
    os << "[";
    for(int i=0;i<UN;++i){
        os << h[i];
        if(i + 1 == UN) os << "]";
        else os << ",";
    }
    return os;
}

vector<hash_t> Power; // 进制的幂值
void initPower(int n){
    Power.clear();
    Power.reserve(n + 1);
    Power.emplace_back(ONE);

    for(int i=1;i<=n;++i){
        Power.emplace_back(Power.back() * Seeds);
    }

    return;
}

hash_t tr(char c) {
    hash_t ans;
    for(int i=0;i<UN;++i) {
        // ans[i] = c;
        ans[i] = c - 'a' + 1;
    }
    return ans;
}

template<typename IT = string::const_iterator>
struct StrHash
{

/// 
StrHash(IT begin, int n):N(n){
    H.clear();
    H.reserve(N + 1);
    H.emplace_back(ZERO);
    for(int i=1;i<=N;++i){
        H.emplace_back(H.back() * Seeds + tr(*begin++));
    }
    return;
}

/// s[a...b]的哈希, a和b是0-index
hash_t get(int a, int b) const {
    assert(0 <= a and a <= b and b < N);
    // ++a, ++ b;
    // return H[b] - H[a - 1] * Power[b - a + 1];
    return H[b + 1] - H[a] * Power[b - a + 1];
}

vector<hash_t> H;
int N;

};


}

/// 模板偏特化
template<> struct std::hash<ZIFUCHUAN::hash_t> {
    std::size_t operator() (const ZIFUCHUAN::hash_t & p) const {
        std::size_t ret = 0;
        for(auto i : p) ret = ret * 9973 + i;
        return ret;
    }
};

using namespace ZIFUCHUAN;

class Solution {

map<int, unordered_map<hash_t, int>> Map;
vector<int> D;

public:
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        initPower(5E4+100);
        StrHash<> H(target.begin(), target.length());

        for(int i=0,n=words.size();i<n;++i){
            auto h = StrHash<>(words[i].begin(), words[i].length()).get(0, words[i].length() - 1);
            auto it = Map.find(words[i].length());
            if(it == Map.end()){
                it = Map.insert(it, {words[i].length(), {}});
            }

            auto jt = it->second.find(h);
            if(jt == it->second.end()){
                it->second.insert(jt, {h, costs[i]});
            }else{
                jt->second = min(jt->second, costs[i]);
            }
        }            

        int N = target.length();
        D.assign(N + 1, -1);
        D[N] = 0;

        for(int i=N-1;i>=0;--i){
            for(const auto & p : Map){
                int len = p.first;
                if(i + len > N) break;
                if(D[i + len] == -1) continue;

                auto h = H.get(i, i + len - 1);
                auto it = p.second.find(h);
                if(it != p.second.end()){
                    chkmin(D[i], D[i + len] + it->second);
                }
            }
        }
        
        return D[0];
    }

    void chkmin(int & a, int b){
        if(-1 == b) return;
        if(-1 == a or a > b) a = b;
        return;
    }
};